package com.chenken.heap;

import java.util.Comparator;


/**
 * 二叉堆
 * 最大堆，大顶堆
 * 使用数组实现
 * @param <E>
 */
public class BinaryHeap<E> extends AbstractHeap<E> {

	private E[] elements;
	
	private static final int DEFAULT_CAPACITY = 10;
	
	public BinaryHeap(Comparator<E> comparator) {
		super(comparator);
		this.elements = (E[])new Object[DEFAULT_CAPACITY];
	}
	
	public BinaryHeap() {
		this(null);
	}
	
	@Override
	public void clear() {
		for(int i = 0;i<size;i++) {
			elements[i] = null;
		}
		size = 0;
	}

	@Override
	public void add(E element) {
		elementNotNullCheck(element);
		ensureCapacity(size+1);
		
		elements[size++] = element;//元素先加到最后面
		/**
		 * 最后面的元素上滤
		 */
		siftUp(size-1);
	}
	
	/**
	 * 让index位置的元素上滤
	 * @param index
	 */
	private void siftUp(int index) {
//		E e = elements[index];
//		while(index>0) {
//			int pindex = (index-1)>>1;//	计算父节点索引
//			E parent = elements[pindex];
//			/**
			//	 如果比父节点大
//			if(compare(e, parent)>0) {
//				E tmp = elements[index];
//				elements[index] = elements[pindex];
//				elements[pindex] = tmp;
//				
//				index = pindex;
//			}
//		}
		/**
		 * 	优化交换操作
		 */
		E e = elements[index];
		while(index>0) {
			/**
			 * 计算父节点索引
			 */
			int parentIndex = (index-1)>>1;
			
			E parent = elements[parentIndex];
			/**
			 *  如果比父节点小，退出循环
			 */
			if(compare(e, parent)<=0) {
				break;
			}
			elements[index] = parent;//将父节点元素存储在index位置
			index = parentIndex;
		}
		elements[index] = e;
	}
	
	@Override
	public E get() {
		emptyCheck();
		return elements[0];
	}

	@Override
	public E remove() {
		emptyCheck();
		
		int lastIndex = --size;
		E root = elements[0];
		elements[0] = elements[lastIndex];
		elements[lastIndex] = null;
		siftDown(0);//	下滤
		return root;
	}
	
	private void siftDown(int index) {
		E element = elements[index];
		/**
		 *  非叶子节点的数量
		 */
		int half = size >> 1;
		//index	< 第一个叶子节点的索引
		//	要保证index的位置是非叶子节点
		while(index	< half) {
			/* 
			 * 完全二叉树的非叶子节点有2种情况
			*	1.只有左子节点
			*	2.有左右2个子节点
			*/
			
			/**
			 *  左子节点索引
			 */
			int childIndex = (index << 1) +1;
			E child = elements[childIndex];
			/**
			 *  右子节点索引
			 */
			int rightChildIndex = childIndex+1;
			/**
			 *  右子节点索引在正常范围内并且右子节点元素大于左子节点
			 */
			E rightChild = elements[rightChildIndex];
			if(rightChildIndex < size && compare(rightChild, child)>0) {
				childIndex = rightChildIndex;
				child = rightChild;
			}
			if(compare(element, child)>0) {
				break;
			}
			/**
			 * 	将子节点存放到index位置
			 */
			elements[index] = child;
			/**
			 *  重新设置index
			 */
			index = childIndex;
		}
		elements[index] = element;
	}

	@Override
	public E replace(E element) {
		elementNotNullCheck(element);
		E root = null;
		/**
		 * 堆是空的
		 */
		if(size == 0) {
			elements[0] = element;
			size++;
		}else {
			root = elements[0];
			elements[0] = element;
			siftDown(0);
		}
		return root;
	}

	private void emptyCheck() {
		if(size == 0) {
			throw new IndexOutOfBoundsException("Heap is empty");
		}
	}
	
	private void elementNotNullCheck(E element) {
		if(element == null) {
			throw new IllegalArgumentException("element must not be null");
		}
	}
	
	/**
	 * 扩容
	 * @param capacity
	 */
	private void ensureCapacity(int capacity) {
		int oldCapacity = elements.length;
		
		if(oldCapacity>=capacity) {
			return;
		}
		/**
		 *  扩容1.5倍
		 */
		int newCapacity = oldCapacity + (oldCapacity>>1);
		E[] newElements = (E[]) new Object[newCapacity];
		for(int i = 0;i<size;i++) {
			newElements[i] = elements[i];
		}
		elements = newElements;
	}

}
